#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
//method 1
void calWaterHelper(int &ans, stack<int> &myStack, int his[], int i)
{
    while(!myStack.empty() && his[myStack.top()] < his[i]) {       
        int top = myStack.top();
        myStack.pop();
        int area  = 0;
        if (!myStack.empty()) 
            area = (min(his[myStack.top()], his[i]) - his[top]) * (i - myStack.top() -1 );
        ans += area;     
    }
    myStack.push(i);
}

int calWater1(int his[], int size)
{
    stack<int> myStack;
    myStack.push(0);
    int ans = 0;

    for (int i = 1; i < size; i++) {
        int top = myStack.top();
        if (his[i] <= his[top]) myStack.push(i);
        else { 
            //cout <<"Cal for" << i << endl;
            calWaterHelper(ans, myStack, his, i); 
        }

    }
    return ans;
}

//method 2 o(1) space
int calWater2(int his[], int size)
{
    int ans = 0;
    int h = 0;
    for (int i = 0; i < size; i++) {
        if (his[i] > his[h]) h = i;
    }

    int left = his[0];
    for (int i = 0; i < h; i++) {
        if (his[i] > left) {
            left = his[i];
        } else {
            ans += left - his[i];
        }
    }

    int right = his[size-1];
    for (int i = size-1; i > h; i--) {
        if (his[i] > right) {
            right = his[i];
        } else {
            ans += right - his[i];
        }
    }

    return ans;
}

//method 3 from wjiang 
int calWater(int his[], int size)
{
    int ans = 0;
    vector<int> high(size, 0);
    int curMax = his[0];
    
    //scan from left to right 
    for (int i = 1; i < size -1; i++) {
       if (curMax <= his[i]) {
           high[i] = his[i];
           curMax = his[i];
       }
       else high[i] = curMax; 
    }

    //scan from right to left
    curMax = his[size-1];
    for (int i = size -2; i > 0; i--) {
        if (curMax <= his[i]) {
            curMax = his[i];
        } 
        high[i] = min(high[i], curMax);
    }

    for (int i = 1; i < size-1; i++) {
        //cout << high[i] << " " ;
        ans += high[i] - his[i];
    }

    return ans;
}


int main(int argc, char **argv)
{
    int result;

    cout <<"----------Test 1------------" << endl;
    int histo1[] = {3,1,5};
    result = calWater(histo1, sizeof(histo1)/sizeof(int));
    cout << result << endl;
    

    cout <<"----------Test 2------------" << endl;
    int histo2[] = {3,1,0,5};
    result = calWater(histo2, sizeof(histo2)/sizeof(int));
    cout << result << endl;

    cout <<"----------Test 3------------" << endl;
    int histo3[] = {3,2,1};
    result = calWater(histo3, sizeof(histo3)/sizeof(int));
    cout << result << endl;


    cout <<"----------Test 4------------" << endl;
    int histo4[] = {1,2,3,2,1};
    result = calWater(histo4, sizeof(histo4)/sizeof(int));
    cout << result << endl;


    cout <<"----------Test 5------------" << endl;
    int histo5[] = {5,4,3,6,2,3};
    result = calWater(histo5, sizeof(histo5)/sizeof(int));
    cout << result << endl;

    cout <<"----------Test 6------------" << endl;
    int histo6[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    result = calWater(histo6, sizeof(histo6)/sizeof(int));
    cout << result << endl;
}
